package item60;

/**
 * @author Lv Jing
 * @date 2018年08月09日 23:50
 */
public class IsBalanceTree {

    /**
     * 面试题60：输入一棵二叉树，判断该二叉树是否是平衡二叉树。
     * 思路：平衡二叉树的特点就是任意节点的左右子树高度差不得超过1，可以通过这一特点，判断节点的高度来做决策
     */
    public class Solution {
        public boolean IsBalanced_Solution(TreeNode root) {
            if (root == null)
                return true;

            int diffDepth = treeDepth(root.left) - treeDepth(root.right);
            // 高度差超过1
            if (diffDepth < -1 || diffDepth > 1)
                return false;
            // 在判断以左右节点为根节点是否保持平衡
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }

        private int treeDepth(TreeNode node) {
            if (node == null)
                return 0;
            int rightDepth = treeDepth(node.right);
            int leftDepth = treeDepth(node.left);
            if (rightDepth > leftDepth)
                return rightDepth + 1;
            return leftDepth + 1;
        }
    }

    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
